Convoluție (informatică)

În informatică, în special în limbajele formale, convoluția (câteodată numită și zip) este o funcție care pune în corespondență o listă de caractere dintr-o secvență cu o secvență de liste de caractere.

Definiție

Fie Σ un alfabet și # un simbol care nu aparține lui Σ.

Fie x₁x₂... x_|x|, y₁y₂... y_|y|, z₁z₂... z_|z|, ... n cuvinte (adică n secvențe finite) de elemente din Σ. Fie $\ell$ lungimea celui mai lung cuvânt, adică maximul dintre |x|, |y|, |z|, ... .

Convoluția acestor cuvinte este o secvență finită de n caractere din (Σ ∪ {#}), adică un element din $((\Sigma \cup \{\#\})^{n})^{*}$:

$(x_{1},y_{1},\ldots )(x_{2},y_{2},\ldots )\ldots (x_{\ell },y_{\ell },\ldots )$,

în care, pentru oricare index i > |w|, w_i este #.

Convoluția celor x, y, z, ... elemente este notatată prin conv( x, y, z, ...), zip( x, y, z, ...) sau x ⋆ y ⋆ z ⋆ ...

Inversa convoluției este câteodată notată cu unzip.

O variantă a operației de convoluție este definită de:

$(x_{1},y_{1},\ldots )(x_{2},y_{2},\ldots )\ldots (x_{\underline {\ell }},y_{\underline {\ell }},\ldots )$

în care ${\underline {\ell }}$ este lungimea minimă a cuvintelor din listă. Acest mod de definire a convoluției elimină folosirea elementului $\#$, dar distruge informația conținută de elementele cu lungime mai mare decât ${\underline {\ell }}$.

Exemplu

Convoluția cuvintelor cum, diez, am este:

$(c,d,a)(u,i,m)(m,e,\#)(\#,z,\#)$

Format:Planetmath